#ifndef linkedlist_h
#define linkedlist_h
#include <utility>

/**
 * leetcode's Definition for singly-linked list.
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ostream & operator << (ostream & out, const ListNode & node){
    return out << node.val;
}
ostream & operator << (ostream & out, const ListNode * node){
    out << "[";
    while(node){ out
        << "\n → 0x" << hex << (int64_t)node
        << "=\"" << dec << node->val << "\"";
        node = node->next;
    } out << " ]";
    return out;
}

// 链表相关函数命名空间
namespace LinkedList{
    
ListNode* Link(vector<int> &vals, vector<ListNode> *list){
    list->reserve(vals.size());
    ListNode *p = NULL;
    for(auto&v:vals){
        list->push_back(ListNode(v));
        if(p) p->next = &*(list->rbegin());
        p = &*(list->rbegin());
    }
    return list->size() ? &((*list)[0]) : NULL;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode emptyHead, *pre = &emptyHead;
    while(l1 && l2){
        auto s = (l1->val <= l2->val ? &l1 : &l2);
        pre->next = *s;
        pre = *s;
        *s = (*s)->next;
    }
    pre->next = (l1 ? l1 : l2);
    return emptyHead.next;
}

ListNode* reverseList(ListNode* head) {
    if(!head || !head->next) return head;
    auto r = head->next;
    head->next = NULL;
    
    while(r->next){
        auto N = r->next; r->next = head;
        head   = r;       r = N;
    }
    
    r->next = head;
    return r;
}

std::pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) {
    if(!tail) return {head, NULL};
    auto ok = tail->next, todo = head;
    while(todo){
        auto ntd = todo->next;
        todo->next = ok;
        ok = todo;
        todo = ntd;
    }
    return {tail, head};
}

}; // namespace LinkedList
#endif /* linkedlist_h */
